class Solution:
    def intToRoman(self, num: int) -> str:
        if num == 0: return ''
        h = {
            1000:'M',
            500:'D',
            100:'C',
            50:'L',
            10:'X',
            5:'V',
            1:'I'
        }
        ha = {
            '900':'CM',
            '400':'CD',
            '90':'XC',
            '40':'XL',
            '9':'IX',
            '4':'IV'
        }
        s = str(num)
        if s[0] == '4' or s[0] == '9':
            for key, val in ha.items():
                if len(s) >= len(key) and s[0:len(key)] >= key:
                    return val + self.intToRoman(num-int(key))
        else:
            for key, val in h.items():
                if num > key: return val + self.intToRoman(num-key)


if __name__ == '__main__':
    s = Solution()
    r = s.intToRoman(58)
    print(r)